package arithmetic;

import java.util.HashMap;
import java.util.Map;


public class Test2 {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.get(2);
        lruCache.put(2,6);
        lruCache.get(1);
        lruCache.put(1,5);
        lruCache.put(1,2);
        lruCache.get(1);
        int i = lruCache.get(2);
        System.out.println(1);

    }


    public static class LRUCache {
        int capacity;
        int curCapacity;
        Map<Integer, ListNode> cacheMap = new HashMap<>(capacity);
        // 定义哨兵节点，在操作链表的时候可以不用考虑边界情况（前后为null的情况）
        ListNode head = new ListNode(-1,-1);
        ListNode tail = new ListNode(-1,-1);

        public void put(int key, int value) {
            //判断节点是否重复添加
            ListNode existNode = cacheMap.get(key);
            if (existNode != null) {
                removeNode(existNode);
                curCapacity--;
            }
            //双向链表存储节点,新增直接放到头部（head的下一个）
            ListNode node = new ListNode(key, value);
            addTohead(node);
            //链表长度+1
            curCapacity++;
            //如果长度超出限制，删除尾部元素和map数据
            if (curCapacity > capacity) {
                cacheMap.remove(tail.pre.key);
                removeTailNode();
                curCapacity--;
            }
            //hash表存储数据
            cacheMap.put(key, node);
        }


        public int get(int key) {
            //从hash表获取数据
            ListNode node = cacheMap.get(key);
            if (node == null) {
                return -1;
            }
            //删除节点
            removeNode(node);
            //移动节点到头部
            addTohead(node);
            return node.value;
        }


        // 定义节点
        public class ListNode {
            int key;
            int value;
            ListNode pre;
            ListNode next;

            ListNode(int key, int value, ListNode pre, ListNode next) {
                this.key = key;
                this.value = value;
                this.pre = pre;
                this.next = next;
            }

            ListNode() {
            }

            ListNode( int key,int value) {
                this.key = key;
                this.value = value;
            }
        }

        //构造函数
        public LRUCache(int capacity) {
            this.capacity = capacity;
            initListNode();
        }


        //初始化链表
        public void initListNode() {
            head.next = tail;
            tail.pre = head;
        }


        public void addTohead(ListNode node) {
            ListNode temp = head.next;
            node.pre = head;
            node.next = temp;
            temp.pre = node;
            head.next = node;
        }

        public void removeTailNode() {
            ListNode pre = tail.pre.pre;
            pre.next = tail;
            tail.pre = pre;
        }

        public void removeNode(ListNode node) {
            ListNode pre = node.pre;
            ListNode next = node.next;
            pre.next = next;
            next.pre = pre;
        }
    }

}